Search for: All records

Finding optimal bipartite matchings—e.g., matching medical students to hospitals for residency, items to buyers in an auction, or papers to reviewers for peer review—is a fundamental combinatorial optimization problem. We found a distributed algorithm for computing matchings by studying the development of the neuromuscular circuit. The neuromuscular circuit can be viewed as a bipartite graph formed between motor neurons and muscle fibers. In newborn animals, neurons and fibers are densely connected, but after development, each fiber is typically matched (i.e., connected) to exactly one neuron. We cast this synaptic pruning process as a distributed matching (or assignment) algorithm, where motor neurons “compete” with each other to “win” muscle fibers. We show that this algorithm is simple to implement, theoretically sound, and effective in practice when evaluated on real-world bipartite matching problems. Thus, insights from the development of neural circuits can inform the design of algorithms for fundamental computational problems. 

Abstract Much of the visual diversity of angiosperms is due to the frequent evolution of novel pigmentation patterns in flowers. The gene network responsible for anthocyanin pigmentation, in particular, has become a model for investigating how genetic changes give rise to phenotypic innovation. In the monkeyflower genus Mimulus, an evolutionarily recent gain of petal lobe anthocyanin pigmentation in M. luteus var. variegatus was previously mapped to genomic region pla2. Here, we use sequence and expression analysis, followed by transgenic manipulation of gene expression, to identify MYB5a—orthologous to the NEGAN transcriptional activator from M. lewisii—as the gene responsible for the transition to anthocyanin-pigmented petals in M. l. variegatus. In other monkeyflower taxa, MYB5a/NEGAN is part of a reaction-diffusion network that produces semi-repeating spotting patterns, such as the array of spots in the nectar guides of both M. lewisii and M. guttatus. Its co-option for the evolution of an apparently non-patterned trait—the solid petal lobe pigmentation of M. l. variegatus—illustrates how reaction-diffusion can contribute to evolutionary novelty in non-obvious ways. Transcriptome sequencing of a MYB5a RNAi line of M. l. variegatus reveals that this genetically simple change, which we hypothesize to be a regulatory mutation in cis to MYB5a, has cascading effects on gene expression, not only on the enzyme-encoding genes traditionally thought of as the targets of MYB5a but also on all of its known partners in the anthocyanin regulatory network.